package com.kevin.Code.Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Vinlee Xiao
 * @Classname DailyTemperatures
 * @Description Leetcode 739 每日温度 中等难度 中频 和接雨水  最大柱形图问题问题有点像
 * @Date 2021/11/19 9:30
 * @Version 1.0
 */
public class DailyTemperatures {

    /**
     * 暴力法：效率低
     * 自己思路：双指针
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {

        int len = temperatures.length;

        if (len == 1) {
            return new int[]{0};
        }
        int[] result = new int[len];
        int left = 0;
        int right = 1;

        while (right < len) {

            while (right < len && temperatures[right] <= temperatures[left]) {

                right++;
            }

            if (right < len) {
                result[left] = right - left;
            } else {
                result[left] = 0;
            }

            left++;
            right = left + 1;
        }
        return result;
    }


    /**
     * 单调栈：右边第一个比当前数大或者小的数
     */
    public int[] dailyTemperatures1(int[] temperatures) {

        int len = temperatures.length;
        int[] result = new int[len];

        //单调栈思想
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < len; i++) {

            int tmp = temperatures[i];
            //如果当前元素值大于栈顶的元素，则弹出元素，
            while (!deque.isEmpty() && tmp > temperatures[deque.peek()]) {

                Integer index = deque.pop();
                result[index] = i - index;
            }
            deque.push(i);

        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{30, 60, 90};
        DailyTemperatures dailyTemperatures = new DailyTemperatures();
        int[] temperatures = dailyTemperatures.dailyTemperatures(nums);
        for (int i : temperatures) {
            System.out.print(i + " ");
        }
    }
}
